#include "stdafx.h"
#include "Graph.h"
#include "MaxWeightStuff.h"
#include "PrintUtils.h"
//#include "PrintUtils.h"

using namespace std;

namespace GraphTools
{

	//string digit2str(const int i)
	//{
	//	switch (i)
	//	{
	//	case 0: 
	//		return "0";
	//	case 1: 
	//		return "1";
	//	case 2: 
	//		return "2";
	//	case 3: 
	//		return "3";
	//	case 4: 
	//		return "4";
	//	case 5: 
	//		return "5";
	//	case 6: 
	//		return "6";
	//	case 7: 
	//		return "7";
	//	case 8: 
	//		return "8";
	//	case 9: 
	//		return "9";
	//	default: 
	//		return "oops";
	//	}
	//}

	//string int2str(const int i)
	//{
	//	if (i == 0)
	//		return "0";
	//	string out = "";
	//	int c = abs(i);
	//	while (c != 0)
	//	{
	//		out = digit2str(c % 10) + out;
	//		//if (c == c / 10)
	//		//	break;
	//		c = c / 10;
	//	}
	//	return i > 0 ? out : "-" + out;
	//}

	Graph::Graph()
		: Vertices(map<string, ptr<Vertex>>()), repetition_treshold(3), maybe_repited_vertex(list<weak_ptr<Vertex>>())
	{}

	Graph::Graph(int repetition_threshold)
	: Vertices(map<string, ptr<Vertex>>()), repetition_treshold(repetition_threshold), maybe_repited_vertex(list<weak_ptr<Vertex>>())
	{}

	int Graph::IndexOf(weak_ptr<Vertex> v)
	{
		auto vertices = this->verticesSorted;
		for (unsigned i = 0; i < vertices.size(); i++)
		{
			if (vertices[i]._Get() == v._Get())
				return i;
		}
		return -1;
	}

	void Graph::AddEdge(string start, string end, int weight)
	{
		auto maybe_start = this->Vertices.find(start);
		auto maybe_end = this->Vertices.find(end);

		ptr<Vertex> start_v, end_v;

		if (maybe_start != Vertices.end())
		{
			start_v = maybe_start->second;
		}
		else
		{
			start_v = ptr<Vertex>(new Vertex(start));
			this->Vertices[start] = start_v;
		}

		if (maybe_end != Vertices.end())
		{
			end_v = maybe_end->second;
		}
		else
		{
			end_v = ptr<Vertex>(new Vertex(end));
			this->Vertices[end] = end_v;
		}

		new Edge(start_v, end_v, weight);
		if (start_v->GetDegree() == repetition_treshold)
			this->maybe_repited_vertex.push_back(start_v);
		if (end_v->GetDegree() == repetition_treshold)
			this->maybe_repited_vertex.push_back(end_v);
	}

	string Graph::RemoveIsolatedNodes()
	{
		string res = "List of isolated nodes:\n";
		int i = 0;
		list<map<string,ptr<Vertex>>::iterator> isolated_to_remove;// = list<map<string,ptr<Vertex>>::iterator>();
		for (auto ite = this->Vertices.begin(); ite != this->Vertices.end(); ite++)
		{
			if (ite->second->GetDegree() <= 0)
			{
			/*	cout << i++ << " found isolated node " << ite->first << endl;*/
				isolated_to_remove.push_back(ite);
			}
		}
		for (auto ite = isolated_to_remove.begin(); ite != isolated_to_remove.end(); ite++)
		{
			if (!(*ite)->second->IsRepeated())
			{
				res += (*ite)->second->GetName() + "\n";
			}
			this->Vertices.erase(*ite);;
		}

		for (auto ite = this->Vertices.begin(); ite != Vertices.end(); ++ite)
		{
			this->verticesSorted.push_back(ite->second);
		}
		return res;
	}

	string Graph::RemoveRepetitions(int percentage)
	{
		string res = "";
		res += "List of Repeat nodes:\n";

		double percentage_threshold = ((double) percentage) / 100.0;
		list<weak_ptr<Vertex>> repetition_to_remove;// = list<weak_ptr<Vertex>>();
		for (auto ite = this->maybe_repited_vertex.begin(); ite != this->maybe_repited_vertex.end(); ite++)
		{
			auto v = ite->_Get(); 
			double v_repetition_threshold = (double)v->GetWeightSum() * percentage_threshold;
			
			if (v->GetFirstWeight() < v_repetition_threshold || v->GetSecondWeight() < v_repetition_threshold)
			{
				//repeted node
				repetition_to_remove.push_back(weak_ptr<Vertex>(*ite));
				res = res + ite->_Get()->GetName() + "\t";
				auto edges = ite->_Get()->GetEdges();
				for (auto e_ite = edges.begin(); e_ite != edges.end(); ++e_ite)
				{
					res = res + PrintUtils::int2str((*e_ite)->GetWeight()) + " ";
				}
				res += "\n";
				//cout << (*ite)._Get()->ToString();

			}
		}
		for (auto ite = repetition_to_remove.begin(); ite != repetition_to_remove.end(); ite++)
		{
			ite->_Get()->SetRepeated(true);
			auto edges = (*ite)._Get()->GetEdges();
			//cout << ite->_Get()->GetName() << " ";
			for (auto e_ite = edges.begin(); e_ite != edges.end(); e_ite++)
			{
				(*e_ite)->DestroyEdge();
			}
		}
		//maybe_repited_vertex.erase(maybe_repited_vertex.begin(), maybe_repited_vertex.end());
		res += this->RemoveIsolatedNodes();
		return res;
	}

	void Graph::ResetFlags()
	{
		for (auto ite = this->Vertices.begin(); ite != this->Vertices.end(); ite++)
		{
			ite->second->SetFlag(false);
		}

	}

	void Graph::BreadthFirstVisit()
	{
		this->ResetFlags();
		queue<Vertex*> to_visit = queue<Vertex*>();
		Vertex* ite;
		to_visit.push(this->Vertices.begin()->second.get());
		while (to_visit.size() > 0)
		{
			ite = to_visit.front();
			to_visit.pop();
			ite->SetFlag(-1);
			//cout << ite->GetName() << endl;
			auto nei = ite->GetNeighbours();
			for (auto n_ite = nei.begin(); n_ite != nei.end(); n_ite++)
			{
				if (!n_ite->_Get()->GetFlag())
				{
					to_visit.push((*n_ite)._Get());
				}
			}
		}
	}

	bool Graph::ValidateGraph()
	{
		int v = this->Vertices.size();
		bool eq = this->Vertices.size() == this->verticesSorted.size();

		for (auto ite = this->Vertices.begin(); ite != this->Vertices.end(); ite++)
		{
			auto edges = ite->second->GetEdges();
			for (auto e_ite = edges.begin(); e_ite != edges.end(); e_ite++)
			{
				if ((*e_ite)->GetWeight() < 0)
				{
					//cout << "so cojon \n";
					return false;
				}
				auto ts = (*e_ite)->GetTerminals();
				auto a = ts.front()._Get()->GetDegree();
				auto b = ts.back()._Get()->GetDegree();
			}
			if (ite->second->GetDegree() != ite->second->GetNeighbours().size())
			{
				//cout << "dimension error \n";
				return false;
			}
		}
		return true;
	}

	const map<string, ptr<Vertex>> Graph::GetVertices()
	{
		return this->Vertices;
	}

	void Graph::SetToEdmonds()
	{
		for (auto ite = this->Vertices.begin(); ite != this->Vertices.end(); ++ite)
		{
			list<ptr<Edge>> to_remove = list<ptr<Edge>>();
			ptr<Vertex> v = ite->second;
			int start = this->IndexOf(v);
			auto edges = v->GetEdges();
			for (auto e_ite = edges.begin(); e_ite != edges.end(); ++e_ite)
			{
				auto edge = *e_ite;
				int end = -1;
				int weight = edge->GetWeight();
				to_remove.push_back(edge);
				auto terminals = edge->GetTerminals();
				if (v.get() == terminals.front()._Get())
				{
					end = this->IndexOf(terminals.back());
				}
				else
				{
					end = this->IndexOf(terminals.front());
				}
				ptr<EdmondsEdge> edmond_edge = ptr<EdmondsEdge>(new EdmondsEdge(start, end, weight));
				this->edmondReduction.push_back(edmond_edge);
			}
			for (auto e_ite = to_remove.begin(); e_ite != to_remove.end(); ++e_ite)
			{
				e_ite->get()->DestroyEdge();
			}
		}
	}

	void Graph::SetFromEdmonds()
	{
		for (unsigned i = 0; i < this->edmondSelected.size(); i++)
		{
			auto edge = *edmondSelected[i];
			ptr<Vertex> start = verticesSorted[edge[0]];
			ptr<Vertex> end = verticesSorted[edge[1]];
			int weight = edge[2];
			new Edge(start, end, weight);
		}
	}

	bool IsSelected(vector<pair<int, int>> pairs, ptr<EdmondsEdge> edge)
	{
		for (auto ite = pairs.begin(); ite != pairs.end(); ++ite)
		{
			auto elem = *ite;
			if (edge->isEquivalent(elem.first, elem.second))
				return true;
		}
		return false;
	}

	void Graph::InterpreteEdmonds(vector<pair<int, int>>  res)
	{
		//if (res.size() != this->verticesSorted.size())
		//	cout << "error in matching";
		//vector<bool> matched = vector<bool>(this->verticesSorted.size());
		vector<pair<int,int>> indexes = res;
		//for (unsigned i = 0; i < res.size(); i++)
		//{
		//	matched[i] = false;
		//}

		//for (unsigned i = 0; i < res.size(); i++)
		//{
		//	if (res[i] != -1 && !matched[i])
		//	{
		//		if (matched[i])
		//		matched[i] = true;
		//		matched[res[i]] = true;
		//		indexes.push_back(pair<int,int>(i, res[i]));
		//	}
		//}

		//pair<int, int> a

		list<ptr<EdmondsEdge>> still_aviable = list<ptr<EdmondsEdge>>();

		for (unsigned i = 0; i < this->edmondReduction.size(); i++)
		{
			if (IsSelected(indexes, edmondReduction[i]))
			{
				this->edmondSelected.push_back(edmondReduction[i]);
			}
			else
			{
				still_aviable.push_back(edmondReduction[i]);
			}
		}

		//this->edmondReduction.clear();
		//for (auto ite = still_aviable.begin(); ite != still_aviable.end(); ++ite)
		//{
		//	auto elem = *ite;
		//	this->edmondReduction.push_back(elem);
		//}
		//return ;
	}

	vector<pair<int, int>> Graph::ApplyEdmondsMaximumMatching()
	{
		vector<EdmondsEdge> edges = vector<EdmondsEdge>(this->edmondReduction.size());
		for (int i = 0; i < edges.size(); i++)
		{
			edges[i] = *this->edmondReduction[i];
			if (edges[i][0] == edges[i][1])
				throw "error";
		}

		auto res = SiloachReducer::DCWMSResolver(this->verticesSorted.size(), edges, 2).Resolve();
		//ptr<MaxWeightStuff::MaxWeightedResolver> resolver = ptr<MaxWeightStuff::MaxWeightedResolver>(new MaxWeightStuff::MaxWeightedResolver());
		//auto res = resolver->MaxWeightedMatching(edges);
		return res;
	}

	void Graph::ReduceEdges()
	{
		//vector<int> degrees = vector<int>(verticesSorted.size());
		//for (int i = 0; i < this->verticesSorted.size(); i++)
		//{
		//	degrees[i] = verticesSorted[i]->GetDegree();
		//}
		this->SetToEdmonds();


		//fstream file_out("primo_giro.txt", ios::out);

		//file_out << "[" << this->edmondReduction[0]->ToString();
		//for (int i = 1; i < this->edmondReduction.size(); i++)
		//{
		//	file_out << ", " << this->edmondReduction[i]->ToString();
		//}
		//file_out << "]";
		//file_out.close();
#if FAST
		cout << "speedup cutter";
		this->edmondSelected = this->edmondReduction;
		cout << "speedup cutter";
#else
		auto match = this->ApplyEdmondsMaximumMatching();
		this->InterpreteEdmonds(match);
#endif
		
		//fstream sfile_out("secondo_giro.txt", ios::out);

		//sfile_out << "[" << this->edmondReduction[0]->ToString();
		//for (int i = 1; i < this->edmondReduction.size(); i++)
		//{
		//	sfile_out << ", " << this->edmondReduction[i]->ToString();
		//}
		//sfile_out << "]";
		//sfile_out.close();

		//match = this->ApplyEdmondsMaximumMatching();
		//this->InterpreteEdmonds(match);
		
		//fstream file_out("primo_giro.txt", ios::out);

		//file_out << this->edmondSelected[0]->ToString();
		//for (int i = 1; i < this->edmondSelected.size(); i++)
		//{
		//	file_out << this->edmondSelected[i]->ToString();
		//}
		//file_out.close();

		this->SetFromEdmonds();

		//for (int i = 0; i < this->verticesSorted.size(); i++)
		//{
		//	if (degrees[i] != verticesSorted[i]->GetDegree())
		//		cout << "error";
		//}

		/*for (auto ite = Vertices.begin(); ite != Vertices.end(); ite++)
		{
			ite->second->ReduceDegreeToTwo();
		}*/
	}

	list<ptr<Scaffold>> Graph::GetScaffolds()
	{
		return this->scaffolds;
	}

	void Graph::CreateScaffolds()
	{
		int i = 0;
		ResetFlags();
		for (auto ite = Vertices.begin(); ite != Vertices.end(); ++ite)
		{
			if (ite->second->GetFlag())
				continue;
			//if (ite->first == "SL2.30ct10972")
				//cout << "ehm\n";
			//cout << i++ << " ";
			ptr<Scaffold> s = ptr<Scaffold>(new Scaffold(ite->second.get()));
			/*s->CreateFrom(ite->second.get());*/
			this->scaffolds.push_back(s);
		}

		this->scaffolds.sort(([=](ptr<Scaffold> s1, ptr<Scaffold> s2){return s1->GetWeight() > s2->GetWeight();}));

		int count = 0;
		for (auto ite = this->scaffolds.begin(); ite != this->scaffolds.end(); ++ite)
		{
			(*ite)->RenameOrdinal(count++);
		}


		//cout << "sorted";
		//auto b = Vertices["SL2.30ct10972"];

	}

}